package TenkindsOfAlgorithm.dynamicProgramming;

/**
 * question 给定一个数组arr={3,34,4,12,5,2}
 * 查看其中任意数字之和为 9
 */
public class Question2SubSet {
    public static void main(String[] args) {
        int []arr={3,34,4,12,5,2};
        boolean b = dp_rec(arr, arr.length - 1, 9);
        System.out.println(b);
        System.out.println(counts);
        System.out.println(dp_subSet(arr, arr.length - 1, 9));
    }
    private static int counts = 0;

    /**
     *
     * @param arr
     * @param i   第几个
     * @param sum  寻找和为9数
     * 出口条件有二个 ： sum==0 && arr[0]==sum
     */
    public static boolean dp_rec(int []arr,int i,int sum){
        counts++;
        if (sum==0 ){
            return true;
        }else if (i==0){
            return arr[0]==sum;
        }else if(arr[i]>sum){
            // 我尝试把这段代码删掉 查看counts的数量 结果超了2倍之多
            return dp_rec(arr,i-1,sum);
        }else  {
            // 有选与不选的操作
            boolean A = dp_rec(arr,i-1,sum-arr[i]);
            boolean B = dp_rec(arr,i-1,sum);
            return A ||B;
        }
    }

    /**
     *仔细查看与上面的代码  递归是从上到下调用函数到出口，再解开。
     * 而我们下面的二维数组记录值是从下到上，递推到过程。
     */
    public static boolean dp_subSet(int[]arr,int i,int sum){
        boolean [][] temp = new boolean[arr.length][sum+1];
        temp[0][arr[0]] = true;
        for (int j = 0; j < arr.length; j++) {
            temp[j][0] = true;
        }
        for (boolean[] row : temp){
            for (boolean data:row){
                System.out.printf("%3b\t",data);
            }
            System.out.println();
        }
        for (int j = 1; j < temp.length; j++) {
            for (int k = 1; k < temp[0].length; k++) {
                if (arr[j]>k){
                    temp[j][k] = temp[j-1][k];
                }else {
                    boolean A = temp[j-1][k-arr[j]];
                    boolean B = temp[j-1][sum];
                    temp[j][k] = A||B;
                }
            }
        }
        System.out.println("after");
        for (boolean[] row : temp){
            for (boolean data:row){
                System.out.printf("%3b\t",data);
            }
            System.out.println();
        }
        return temp[arr.length-1][sum];

    }
}
